package 中等.贪心思想;

import java.util.Arrays;

/**
 * 你正在参加一个多角色游戏，每个角色都有两个主要属性：攻击 和 防御 。
 * 给你一个二维整数数组 properties ，其中 properties{i} = {attacki, defensei}
 * 表示游戏中第 i 个角色的属性。
 * <p>
 * 如果存在一个其他角色的攻击和防御等级 都严格高于 该角色的攻击和防御等级
 * ，则认为该角色为 弱角色 。更正式地，如果认为角色 i 弱于 存在的另一个角色 j ，
 * 那么 attackj > attacki 且 defensej > defensei 。
 * <p>
 * 返回 弱角色 的数量。 
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/the-number-of-weak-characters-in-the-game
 */
public class 游戏中弱角色的数量_1996 {

    public static void main(String[] args) {

        int[][] properties = {{7, 7}, {1, 2}, {9, 7}, {7, 3}, {3, 10}, {9, 8}, {8, 10}, {4, 3}, {1, 5}, {1, 5}};
        System.out.println(numberOfWeakCharacters(properties));

    }

    /**
     * 先排序好攻击力
     * 从小到大排序
     * 判断当前元素是否是弱角色，取决于当前元素之后的元素，是否有防御力大于当前元素的元素
     *
     * @param properties
     * @return
     */
    public static int numberOfWeakCharacters(int[][] properties) {
        int ans = 0;
        Arrays.sort(properties, (o1, o2) -> o1[0] - o2[0]);
        for (int i = 0; i < properties.length; i++) {
            int curValue0 = properties[i][0];
            int curValue1 = properties[i][1];
            int nextIndex = i + 1;
            while (nextIndex < properties.length) {  //找到后面的元素是否大于当前元素
                if (curValue1 < properties[nextIndex][1] && curValue0 < properties[nextIndex][0]) {
                    ans++;
                    break;
                }
                nextIndex++;
            }
        }
        return ans;
    }

    /**
     * 先排序好攻击力
     * 从大到小排序
     * 判断当前元素是否是弱角色，取决于当前元素之前的元素，是否有防御力大于当前元素的元素
     * 那么不需要每次都找后面的元素判断是否比当前大，而是维护一个目前为止，防御力最大的元素
     * 存在一个副作用：
     * 如果最大防御力所在元素攻击力等于当前元素攻击力，那么不能作为依据
     * 排序细节：
     * 对于攻击力相等的元素，防御力按照从小到大进行排序
     * 那么之前防御力最大值，如果大于当前防御力，那么必然攻击力也大于
     *
     * @param properties
     * @return
     */
    public static int numberOfWeakCharacters2(int[][] properties) {
        int ans = 0;
        Arrays.sort(properties, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);

        int maxDefense = properties[0][1];
        for (int i = 1; i < properties.length; i++) {
            if (properties[i][1] < maxDefense) {
                ans++;
            } else {
                maxDefense = properties[i][1];
            }
        }
        return ans;
    }

}
